package com.lwt.codetop.arrayOrSort;

//4. 寻找两个正序数组的中位数

/**
 * 思路：分治，本质求第k小的元素
 */
public class MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        double res = 0;
        int[] nums1 = {1, 2};
        int[] nums2 = {3, 4};
        int total = nums1.length + nums2.length;
        if(total % 2 == 0) {
            int left = f(nums1, 0, nums2, 0, total / 2);
            int right = f(nums1, 0, nums2, 0, total / 2 + 1);
            res = (left + right) / 2.0;
        }else {
            res = f(nums1, 0, nums2, 0, total / 2 + 1);
        }
        System.out.println(res);
    }

    /**
     * 分治法，寻找两个有序数组中的第k小的元素
     * @param nums1
     * @param i
     * @param nums2
     * @param j
     * @param k
     * @return
     */
    private static int f(int[] nums1, int i, int[] nums2, int j, int k) {
        // 为了方便我们默认第一个数组的元素是少的
        if(nums1.length - i > nums2.length - j) return f(nums2, j, nums1, i, k);
        // 当第一个数组用完了(第一个数组是空的，我们要找的就是第二个数组的第k个数，即B[j + k - 1]，k是从1开始的)
        if(nums1.length == i) return nums2[j + k - 1];
        // 当取第一个元素/递归出口--->求第k小，我们取小的返回
        if(k == 1) return Math.min(nums1[i], nums2[j]);

        int si = Math.min(nums1.length, i + k / 2); // A[k/2]的后一个位置 注意；由于A[]的元素可能少，为了防止越界要进行特判
        int sj = j +  k / 2;  // B[k/2]的后一个位置
        // 分治
        if(nums1[si - 1] > nums2[sj - 1]){
            return f(nums1, i, nums2, sj, k - (sj - j));
        }else {
            return f(nums1, si, nums2, j, k - (si - i));
        }
    }
}
